Critical to any object oriented database (ODB) is the concept of persistent object identity. In the most general sense, object identity is an inalienable characteristic of an object which can be used to differentiate the object from all other objects, even if other objects are otherwise similar, and to retrieve the object from a persistent storage device such as a magnetic disk and transfer the object into computer memory.
In theory, any pattern of bits can serve to implement the object identifier (OID), so long as that pattern is never used to implement the identity of any other object. Thus, a machine or system which generates unique bit patterns would be sufficient for providing persistent OIDs so long as the same bit pattern was never generated twice. In practice, performance considerations prefer OIDs that are as small as possible and systems which generate OIDs as quickly as possible.
In a distributed computing system consisting of multiple processors executing multiple client processes and interconnected by a network, there is a special challenge in assuring that each client process can locally assign OIDs that are globally unique across all client processes. Typically three basic approaches to this challenge have been attempted.
In the first approach each client process independently generates globally unique OIDs. One typical technique is to form OIDs by concatenating a processor identifier with a date-time stamp. Since each processor on the network has a unique identifier (for the purpose of network communication) and since the date-time stamp is monotonically increasing, each OID created is guaranteed to be unique. In another approach, each client process independently generates locally unique OIDs, which are then changed to globally unique OIDs (if necessary) by an independent agent, such as a central server. In a third approach to the problem, each client process appeals to an independent agent such as a central server to generate globally unique OIDs each time the client process needs to create an object.
Each of these approaches has performance trade-offs. Because the first approach generates globally unique ids (GUIDs) locally, it saves the expense of network communication with a server or coordinating agent that is incurred by the other approaches. However, the price incurred by this lack of communication is that the OIDs in this approach tend to be large. Larger OIDs require more disk storage and also require more time to read, write, and process.
The second approach generates locally unique OIDs (LUIDs) and when these LUIDs happen to be also recognizably globally unique, this approach performs well. However, problems arise in concurrent environments when the LUIDs must be converted or remapped into GUIDs. The cost of this conversion is at least proportional to the number of newly created objects and may be much greater, since all objects which reference newly created objects must have those references converted from LUID to GUID as well.
The third approach avoids both the conversion expense of the second approach, and the large GUIDs of the first approach. However, performance problems associated with this method result from the more frequent communication with the server or coordinating agent than in either of the other approaches. Such frequent communication causes the performance to degrade very quickly in the presence of a large amount of network traffic.
What is required then is a system which will generate globally unique object identifiers without the large GUID size required of locally generated identifiers, without the performance degradation due to identifier conversion, and without the excessive network traffic which typically accompanies the use of an identification server.